#include <iostream>
#include <fstream>
#include <sstream>

using namespace std;

/*
Serialize a binary tree and save it into a file. Then restore 
it from the file. The tree is not binary search tree. You 
can assume the treenode->Value is integer.  

http://www.leetcode.com/2010/09/serializationdeserialization-of-binary.html
*/
class TreeNode
{
public:
	int Data;
	class TreeNode *lChild;
	class TreeNode *rChild;
};

TreeNode *CreateBT( int *Array, int start, int end )
{
	//
	// Assume the Array is ordered so the new
	// created BT should be BST
	//
	if( start > end )
		return NULL;

	int middle  = start + (end-start)/2; //avoid integer overflow
	TreeNode * node = new TreeNode();
	
	node->Data = Array[middle];
    node->lChild = CreateBT( Array, start, middle-1 );
    node->rChild = CreateBT( Array, middle+1, end );

	return node;
}


void WriteBinaryTree(TreeNode *p, ostream &out) 
{
	if (!p) 
		out << "# ";
	else 
	{
		out << p->Data << " ";
		WriteBinaryTree(p->lChild, out);
		WriteBinaryTree(p->rChild, out);
	}
}

bool ReadNextToken( int &token, string str, int &pos, bool &isNumber )
{
	while( pos < str.length() && str.at(pos) == ' ') 
		pos++;

	if( str.length()-1 == pos )
		return false;

	int start = pos;
	if( str.at(pos) == '#' )
	{
		pos++;
		isNumber = false;
		return true;
	}

	while( pos<str.length() && str.at(pos) != ' ' )
		pos++;
	string number = str.substr(start, pos-start);
	token = atoi(number.c_str());
	cout<<token<<" ";

	return true;
}

void ReadBinaryTree(TreeNode *&p, string str, int &pos) 
{
	int token;
	bool isNumber;

	if (!ReadNextToken(token, str, pos, isNumber))
		return;

	if (isNumber) 
	{
		p = new TreeNode();
		p->Data = token;
		ReadBinaryTree(p->lChild, str, pos);
		ReadBinaryTree(p->rChild, str, pos);
	}
}

int main()
{
	int Array[10] = {1,2,3,4,5,6,7,8,9,10};
	TreeNode *root = CreateBT(Array, 0, 9);
	
	ofstream myfile("myfile.txt");
	WriteBinaryTree( root, myfile );
	myfile.close();

	ifstream in("myfile.txt");
	stringstream buffer;
	buffer << in.rdbuf();
	string contents(buffer.str());	
	TreeNode *root2=NULL;
	int curPosition = 0;
	ReadBinaryTree(root2, contents, curPosition);

	cout<<"\nPress anykey to terminate..."<<endl;
	return getchar();
}